package com.gitee.feizns.explore.data_structure.tree.bs.mid;

/**
 * @author feizns
 * @since 2020/3/19
 */
public class GetTargetCopy {

    public static void main(String[] args) {

    }

    public static final TreeNode getTargetCopy(final TreeNode original, final TreeNode cloned, final TreeNode target) {
        return find(cloned, target);
    }

    private static TreeNode find(TreeNode cloned, TreeNode target) {
        if ( cloned != null ) {
            if ( equals(cloned, target) )
                return cloned;
            TreeNode lef = find(cloned.left, target);
            if ( lef != null )
                return lef;
            return find(cloned.right, target);
        }
        return null;
    }

    private static boolean equals(TreeNode node1, TreeNode node2) {
        if ( node1 == node2 )
            return true;
        else if ( node1 == null || node2 == null )
            return false;
        else if ( node1.val == node2.val )
            return equals(node1.left, node2.left) && equals(node1.right, node2.right);
        return false;
    }

}
